#ifndef GRAPH_H_
#define GRAPH_H_
#include<climits>
#include<iostream>
#include<stack>
#include<list>
#include<vector>
#include<algorithm>
using namespace std;
typedef enum {UNDISCOVERED,DESCOVERED,VISITED} VStatus;//status of vertexes
typedef enum {UNDETERMINED,TREE,CROSS,FORWARD,BARKWARD} EStatus;//status of edges
int findElement(vector<int> v, int key)   ///a function for finding an element and return the index
{
	int len = v.size();
	for(int i=0; i<len; i++){
		if(v.at(i) == key){
			return i;
		}
	}
	return -1;
}
vector <int> tag;///a vector to store integer tags of vertexes

template <typename Tv, typename Te>//type of vertexes and edges
class Graph
{

public:
    virtual void listVertexes()=0;
    virtual void listEdges()=0;
    ///for vertexes
    int n;///number of vertexes
    virtual int insert(Tv const&)=0;///insert a vertex and return aits serial number
    virtual Tv& vertex(int)=0;///confirm existence of the vertex
    virtual int inDegree(int)=0;///indegree of v
    virtual int outDegree(int)=0;///outdegree of v
    virtual VStatus& status(int)=0;///status of v

    ///for edges
    int e;
    virtual bool exists(int, int)=0;///show whether e(u,v) exists
    virtual void insert(Te const&,int,int,int)=0;///insert an edge from u to v with weight
    virtual EStatus status(int,int)=0;///show the status of edge(u,v)
    virtual int weight(int,int)=0;///the weight of edge(u,v)

};

template<typename Tv> struct Vertex
{
    Tv data;int inDegree;int outDegree;VStatus status;
    Vertex(Tv const& d=(Tv)0):data{d},inDegree{0},outDegree{0},status{UNDISCOVERED}{}
};

template<typename Te> struct Edge
{
    Te data;int weight;EStatus status;int index; ///index is specifically used in a list
    Edge(Te const& d,int w):data{d},weight{w},status{UNDETERMINED},index{0}{}
    Edge(Te const& d,int w,int number):data{d},weight{w},status{UNDETERMINED},index{number}{}
    Edge(int w):data{(Te)0},weight{w},status{UNDETERMINED},index{0}{}
};
template<typename Tv,typename Te>
class GraphMatrix:public Graph<Tv, Te>///inplementation of a graph by a matrix consisting of vectors
{
    int n,e;
private:
    vector<Vertex<Tv>> V;     //vector container for vertexes 
    vector<vector<Edge<Te>*>> E;//two-dimensional vector container for edges
public:
    GraphMatrix(){n=e=0;}///constructor
    ~GraphMatrix()///distructor
    {
        for(int j=0;j<n;j++)
        {
            E[j].clear();
        }
        E.clear();
    }
//basics operations for vertex i,where 0<=i<n
    virtual Tv& vertex(int i){return V[i].data;}
    virtual int inDegree(int i){return V[i].inDegree;}
    virtual int outDegree(int i){return V[i].outDegree;}
    virtual VStatus& status(int i){return V[i].status;}
//dynamic operations for vertex i,where 0<=i<n
    virtual int insert(Tv const& vertex)
    {
        for(int j=0;j<n;j++ )
            E[j].push_back(nullptr);
        n++;//prepare edges for every other vertexes
        E.push_back(vector<Edge<Te>*>(n,(Edge<Te>*)nullptr));//here a vector of n edges is constributed 
        V.push_back(Vertex<Tv>(vertex));//construct a Vertex(a struct) space for the new vertex and push it into
        return V.size();
    }
///basic static functions for edges
    virtual bool exists(int i,int j)          ///judge the exitence of E[i][j]
    {return 0<=i&&i<n&&j<n&&E[i][j]!=nullptr&&i!=j;}
    virtual EStatus status(int i,int j){return E[i][j]->status;}
    /**
    *The function below is not added none-null condition because I don't want
    *to convert the returned value of a lvalue,so the limiting condition would
    *be exerted out of the function
    */
    virtual Te& edge(int i,int j)  
    {
        return E[i][j]->data;
    }
    virtual int weight(int i,int j)
    { 
        if(exists(i,j)) 
            return E[i][j]->weight;
        return 1;
    }

///basic dynamic functions for edges
    virtual void insert(Te const& edge,int w,int i,int j)
    {
        if(exists(i,j)) return;
        if(i<0||i>=n||j<0||j>=n||i==j) return;
        E[i][j]=new Edge<Te>(edge,w);
        e++;V[i].outDegree++;V[j].inDegree++;
    }
    virtual void listVertexes()
    {
        for(int i=0;i<n;i++)
            cout<<V[i].data<<" ";
        cout<<endl;
    }
    virtual void listEdges()
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cout<<"i: "<<tag[i]<<" "<<"j "<<tag[j]<<" "<<"weitht: "<<weight(i,j)<<endl;
            }
            
        }
    }
};


template<typename Tv,typename Te>
class GraphList:public Graph<Tv, Te>{///inplementation of a graph by a matrix consisting of vectors
private:
    int n;
    int e;
    vector<Vertex<Tv>> V;///the information of vertexes is still stored by a vector
    vector<list<Edge<Te>*>> E;    ///by a nested vector of list container
    Edge<Te>* orient(int i,int j)      ///a function for locating the edge (i,j)
    {
        typename list<Edge<Te>*>::iterator k;
        for(k=E[i].begin();k!=E[i].end();k++)
        {
            if((*k)->index==j)
                return *k;
        }
        return nullptr;
    }
public:
    GraphList(){n=e=0;}
    ~GraphList()
    {
        for(int i=0;i<n;i++)
        {
            E[i].clear();
        }
        E.clear();
    }
    /**
    /*Deletion operations are skipped because
    /*it's troublesome and not so revelant to 
    /*the request of assignment 
    */
    virtual Tv& vertex(int i){return V[i].data;}
    virtual int inDegree(int i){return V[i].inDegree;}
    virtual int outDegree(int i){return V[i].outDegree;}
    virtual VStatus& status(int i){return V[i].status;}
    virtual int insert(Tv const& vertex)
    {
        list<Edge<Te>*> tmp;
        E.push_back(tmp);
        V.push_back(Vertex<Tv>(vertex));
        n++;
        return n;
    }
    virtual bool exists(int i,int j)
    {
        if(i<0||i>=n||j<0||j>=n||i==j)
            return 0;
        typename list<Edge<Te>*>::iterator k;
        for(k=E[i].begin();k!=E[i].end();k++)
        {
            if(*k==nullptr)
                return 0;
            if((*k)->index==j)
                return 1;
        }
        return 0;
    }
    virtual  EStatus status(int i,int j)
    {
        
        if(exists(i,j))
        {   
            Edge<Te>* p=orient(i,j);
            return p->status;
        }
        return UNDETERMINED;
    }
    virtual Te& edge(int i,int j)
    {
        Edge<Te>* p=orient(i,j);
        return p->data;
    }
    virtual int weight(int i,int j)
    {
        if(exists(i,j))
        {
            Edge<Te>* p=orient(i,j);
            return p->weight;
        }
        return 1;///return 1 when the pointed edge does not exist
    }

    virtual void insert(Te const& edge,int w,int i,int j)
    {
        if(exists(i,j))
            return;
        Edge<Te>* p=new Edge<Te>(edge,w,j);
        E[i].push_back(p);
    }
    virtual void listVertexes()
    {
        for(int i=0;i<n;i++)
            cout<<V[i].data<<" ";
        cout<<endl;
    }
    virtual void listEdges()
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cout<<"i: "<<tag[i]<<" "<<"j "<<tag[j]<<" "<<"weitht: "<<weight(i,j)<<endl;
            }
        }
    }
};
#endif